#include <fstream>
#include <iostream>
#include <list>
#include <string.h>
#include <typeinfo>
#include <stdio.h>

#define DEBUG

/* Todo
 * ====
 * -> Make sure public/protected/private etc delarations are appropriate.
 * -> Change to use printf rather than iostreams (AIE styleguide).
 * -> Other changes to match AIE style-guide.
 * -> Change Context class so it can be initialised with in/out files
 *    rather than setting them later in main().
 * 
 * 
 * Wikipedia http://en.wikipedia.org/wiki/Huffman_coding
 * M.A. Weiss "Data Structures and Algorithm Analysis in C"
 * 
 * Clear about what we are building.
 * 
 * Requirements:
 * 
 * A. 
 * 1. Encode an ascii text file as a binary tree using Huffman coding. Write 
 *    this encoded message out as a binary file.
 * 2. Decode the binary file generate by the above to recover the original
 *    ascii message. 
 * 
 * B. Optional features
 * In addition, I would like the following:
 * 3. An automatic test that the original and recovered messages are identical.
 * 4. Room to extend so that additional encoding methods can be easily added.
 * 5. Room to extend so that the encoding methods can be profiled. Ideally to
 *    test for:
 *      i) compression ratios (test these under various conditions such as 
 *          different kinds of text input and different lengths of input
 *      ii) test for speed,inder the same conditions as for i).
 * 6. Ability to call with command line switches to determine input file, 
 *    output file, and which of the methods in 4 and 5 are to be called.
 * 
 * From wikipedia (http://en.wikipedia.org/wiki/Huffman_coding)
 * Creating the tree:

   1. Start with as many leaves as there are symbols.
   2. Enqueue all leaf nodes into the first queue (by probability in increasing order so that the least likely item is in the head of the queue).
   3. While there is more than one node in the queues:
         1. Dequeue the two nodes with the lowest weight.
         2. Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.
         3. Enqueue the new node into the rear of the second queue.
   4. The remaining node is the root node; the tree has now been generated.
 * 
 * 
 */


//======================
//void HuffmanEncoderToBinary::build_frequency_table(){
//	/* <???> design issue - want to switch here depending on whether we are
//	encoding the file or decoding it. In first case we scan file and calculate
//	frequencies, in latter we just read the table in from the encoded file. */
//		
//	// Use a list from the stl - they can be sorted using a member function.
//	std::list<char> freq_table;
//	// Should probably do some checking here!
//	freq_table.push_front(1);
//	freq_table.push_front(2);
//	
//	#ifdef DEBUG
//	    std::cout << "Finished build_frequency_table" << std::endl;
//	#endif //DEBUG
//	}
//	
//================================
/* void HuffmanEncoderToBinary::Encode(){
	std::ofstream coded_file("coded_message.dat", std::ios::binary | std::ios::out);

	//TreeNode huffman_tree;
	
	int cur_char;
		for (cur_char=0; cur_char<12; ++cur_char){
			//(*m_context.mp_outFile).put(cur_char);
			coded_file.put(cur_char);
		}
	coded_file.close();
	HuffmanEncoderToString::create_huffman_tree();
	std::cout << "Finished HuffmanEncoderToString::Encode()" << std::endl;
	
}
 */
//====================================

	struct TreeNodeElement{
		// Make sure to use relative frequencies here, to avoid overflowing
		// int when messages are long. <???>
	    char character;
	    float frequency; // float? double?
	};   // <???> Is this Python in C++? Use Classes?
	typedef struct TreeNodeElement element; // <???> Use pointer here?
	typedef struct TreeNode *tree_node_ptr;
	
	struct TreeNode{
		TreeNodeElement element;
		tree_node_ptr left_child;
		tree_node_ptr right_child;
	};

//==============================================================================	
class Context
{
public:
    // The 'big four' - constructor, destructor, copy-constructor, and
	// assignment operator.
	Context::Context() {
		std::cout << "Context constructor called." << std::endl;
		}
	Context::Context(const Context& other_context) : m_encodedFilename(other_context.m_encodedFilename) {
		std::cout << "Context copy-constructor called. Not yet implemented. " << std::endl;
		
		}
	Context& Context::operator = (const Context& other_context) {
		std::cout << "Context assignment operator (=) called. Not yet properly implemented." << std::endl;
		Context new_context; 
		return new_context;
		}
	virtual Context::~Context() {
	 			std::cout << "Context destructor called." << std::endl;
	 			}
	
	std::string m_inputFilename;
	std::string m_encodedFilename;
	std::string m_decodedFilename;
};	

//==============================================================================
class Translator
{
	public:
		Context m_context;
        // The 'big four' - constructor, destructor, copy-constructor, and
		// assignment operator.
		Translator::Translator(Context& context) : m_context(context) {
			// The 'Translator' (a strategy) Constructor takes a reference to 
			// the 'Context' (a context) so that it can make callbacks for 
			// other stuff it needs ie the filenames and so on.
			std::cout << "Translator constructor finished." << std::endl;
			}
		Translator::Translator(const Translator& other_translator) {
			std::cout << "Translator copy-constructor called. Not yet implemented. " << std::endl;
			}
		Translator& Translator::operator = (const Translator& other_translator) {
			std::cout << "Translator assignment operator (=) called. Not yet properly implemented." << std::endl;
			// <wsl> Beware!!!
			Context new_context;
			new_context = other_translator.m_context;
			Translator new_translator(new_context); 
			return new_translator;
			}
		virtual Translator::~Translator() {
		 			std::cout << "Translator destructor called." << std::endl;
		 			}
		virtual void Translator::Translate(){
					std::cout << "Translator::Translate() called." << std::endl;
					Translator::TranslateStream();
				}
		virtual void Translator::TranslateStream(){
			std::cout << "Translator::TranslateStream() called." << std::endl;	
		}
}; //class Translator


//==============================================================================
class HuffmanEncoder : public Translator 
{		
	public:
		//Context m_context;
		HuffmanEncoder::HuffmanEncoder(Context  &context) : Translator(context) {
			std::cout << "HuffmanEncoder constructor finished." << std::endl;
		}
		virtual void HuffmanEncoder::Translate();
        virtual void HuffmanEncoder::TranslateStream();
	private:
		void HuffmanEncoder::create_huffman_tree();
		void HuffmanEncoder::build_frequency_table();
		void HuffmanEncoder::build_tree_structure();
};
//==============================================================================
void HuffmanEncoder::Translate(){
			std::cout << "HuffmanEncoder::Translate() called." << std::endl;
			HuffmanEncoder::TranslateStream();
}

void HuffmanEncoder::TranslateStream(){
	
	std::cout << "HuffmanEncoder::TranslateStream() called." << std::endl;	
		
	FILE * pFile;
	
	//pFile = fopen(static_cast<const char*>(m_context.m_encodedFilename.c_str()), "wb");
	//pFile = fopen((m_context.m_encodedFilename.c_str()), "wb");
	pFile = fopen("coded_message.dat", "wb");
	
	
	if (  pFile==NULL  ){
		 std::cerr << "Problem opening encoded file!";
		 exit(8);
	}
	std::cout << "======> HuffmanEncoder::TranslateStream: typeid(pFile).name() is " << typeid(pFile).name() << std::endl;
	
	char buffer[] = {'1','2','3', '4'};
	fwrite(buffer, 1, sizeof(buffer), pFile);
	fclose(pFile);

	std::cout << "Finished HuffmanEncoder::TranslateStream()" << std::endl;

}

void HuffmanEncoder::build_frequency_table(){
	/* <???> design issue - want to switch here depending on whether we are
	encoding the file or decoding it. In first case we scan file and calculate
	frequencies, in latter we just read the table in from the encoded file. */
		
	// Use a list from the stl - they can be sorted using a member function.
	std::list<char> freq_table;
	// Should probably do some checking here!
	freq_table.push_front(1);
	freq_table.push_front(2);
	
	#ifdef DEBUG
	    std::cout << "Finished HuffmanEncoder::build_frequency_table" << std::endl;
	#endif //DEBUG
	}
	
void HuffmanEncoder::build_tree_structure(){	
	#ifdef DEBUG
		std::cout << "Finished HuffmanEncoder::build_tree_structure" << std::endl;
    #endif //DEBUG
}

void HuffmanEncoder::create_huffman_tree(){
	// create huffman tree:
	//    - build frequency table
	//    - sort frequency table
	//    - build tree structure	
	HuffmanEncoder::build_frequency_table();
	HuffmanEncoder::build_tree_structure();
	#ifdef DEBUG
		std::cout << "Finished HuffmanEncoder::create_huffman_tree" << std::endl;
    #endif //DEBUG
}

//==============================================================================
int main(int argc, char* argv[]) {
	
	std::string inputFilename, encodedFilename, decodedFilename;
	
	// Make a 'context'
	Context context;
	// Give it some stuff like the names of the input and output files.
	context.m_encodedFilename = encodedFilename;
	
	//std::string encoding_type = "string";
	std::string encoding_type = "binary";
	
	if(encoding_type == "string") {
		
		// Make an Encoder that will output the Huffmann encoding of an input
		// string as ascii. Pass in our Context object as context.
	
		// Make an object which will encode to a string using a Huffman coding.
		HuffmanEncoder huffmanEncoder(context);
		// Call the Encode() method on our Encoder.
		huffmanEncoder.Translate();
	}
	else if (encoding_type == "binary") {
		
		// Make an Encoder that will output the Huffmann encoding of an input
		// string in our specialised binary format. Pass in our Context 
		// object as context.
	
		// Make an object which will encode to a string using a Huffman coding.
		HuffmanEncoder huffmanEncoder(context);
		// Call the Encode() method on our Encoder.
		huffmanEncoder.Translate();
	}
	
	// Close the files.
	//original_file.close();
	//decoded_file.close();
}



